package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 1955. 统计特殊子序列的数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/13 11:50
 */
public class CountSpecialSubsequences {

    public static void main(String[] args) {
        CountSpecialSubsequences test = new CountSpecialSubsequences();

        // 3
//        int[] arr = {0, 1, 2, 2};

        // 0
//        int[] arr = {2, 2, 0, 0};

        // 7
//        int[] arr = {0, 1, 2, 0, 1, 2};

        // 43
//        int[] arr = {2, 0, 1, 2, 0, 2, 2, 1, 2, 2};

        // 19
//        int[] arr = {2, 0, 1, 2, 0, 2, 2, 1, 2};

        //
        int[] arr = Utils.getArr(100000, 0, 3);

        int i = test.countSpecialSubsequences(arr);
        System.out.println(i);
    }

    public int countSpecialSubsequences(int[] nums) {
        long zero = 0;
        long one = 0;
        long two = 0;
        long oneAll = 0;
        long twoAll = 0;
        for (int num : nums) {
            if (num == 0) {
                zero = ((zero << 1) + 1) % 1000000007;
            } else if (num == 1) {
                if (zero == 0) {
                    continue;
                }
                one = (zero + oneAll) % 1000000007;
                oneAll = (oneAll + one) % 1000000007;
            } else {
                if (one == 0) {
                    continue;
                }
                two = (oneAll + twoAll) % 1000000007;
                twoAll = (twoAll + two) % 1000000007;
            }
        }
        return (int) (twoAll % 1000000007);
    }

}
